#include<string>
#include<unordered_map>
using namespace std;
//struct pair_hash
//{
//    template<class T1, class T2>
//    std::size_t operator() (const std::pair<T1, T2>& p) const
//    {
//        auto h1 = std::hash<T1>{}(p.first);
//        auto h2 = std::hash<T2>{}(p.second);
//        return h1 ^ h2;
//    }
//};

//bool isMatch(const string& s, const string& p, int s_idx, int p_idx, unordered_map<pair<int,int>,bool, pair_hash>&map) {
//    auto key = make_pair(s_idx, p_idx);
//    if (map.find(key) != map.end())
//        return map[key];
//    while (s_idx < s.length() && p_idx < p.length()) {
//        if (p[p_idx]=='?'||s[s_idx] == p[p_idx]) {
//            ++s_idx;
//            ++p_idx;
//            continue;
//        }
//        if (p[p_idx] == '*') {
//            while (p_idx < p.length()&&p[p_idx]=='*') 
//                ++p_idx;
//            if (p_idx >= p.length())
//                return true;
//            while (s_idx < s.length()) {
//                if ((p[p_idx] == '?'||s[s_idx] == p[p_idx]) && isMatch(s, p, s_idx+1, p_idx+1, map))
//                    return true;
//                ++s_idx;
//            }
//        }
//        return false;
//    }
//    while (p_idx < p.length() && p[p_idx] == '*')++p_idx;
//    map[key] = s_idx >= s.length() && p_idx >= p.length();
//    return map[key];
//}
class Solution {

public:
    bool isMatch(string s, string p) {
        vector<bool>dp0(s.length()+1);
        vector<bool>dp1(s.length()+1);
        dp0[0] = true;
        int index0 = 0, index1 = s.length()+1;
        for (int j = 1; j <= p.length(); ++j) {
            for (int i = 0; i <= s.length(); ++i) {
                if (i == 0) {
                    dp1[i] = p[j - 1] == '*' && dp0[i];
                    continue;
                }
                if (p[j-1] == '?' || p[j-1] == s[i-1]) {
                    dp1[i] = dp0[i - 1];
                }
                else if(p[j-1] == '*'&& index0 <=i){
                    dp1[i] = true;
                }
                else {
                    dp1[i] = false;
                }
                if (dp1[i]&& index1 == s.length()+1) {
                    index1 = i;
                }
            }
            swap(dp0, dp1);
            index0 = index1;
            index1 = s.length()+1;
        }
        return dp0[dp0.size()-1];
    }
};

int main() {
    Solution sol;
    sol.isMatch("zacabz",
        "*a?b*");
}